package Dynamic_Programming.package_01;
/*
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。

本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。

确定dp数组（dp table）以及下标的含义
dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背最大重量为dp[j]。
    dp[i][j]
确定递推公式
    不放物品（j<val[i]）： dp[i][j]=dp[i-1][j]
    放物品：dp[i][j]=max(dp[i-1][j],dp[i-1][j-val[i]]+val[i])
dp数组如何初始化
    第一列都是0
    第一行根据物品0的大小来
确定遍历顺序
举例推导dp数组
* */
public class lc1049 {
    public int lastStoneWeightII(int[] stones) {
        int sum=0;
        for (int val:stones
             ) {
            sum+=val;
        }
        int[][] dp=new int[stones.length][sum/2+1];
        //初始化
        for (int i = 0; i <stones.length ; i++) {
            dp[i][0]=0;
        }
        for (int i = stones[0]; i <sum/2+1 ; i++) {
            dp[0][i]=stones[0];
        }
        //遍历
        for (int i = 1; i <stones.length ; i++) {
            for (int j = 0; j < sum/2+1; j++) {
                if(j<stones[i]){
                    dp[i][j]= dp[i-1][j];
                }else {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-stones[i]]+stones[i]);
                }
            }
        }
        return sum-dp[stones.length-1][sum/2]*2;
    }
}
